#!/usr/bin/env python
# encoding: utf-8
"""
MSPrefixSpan.py

Created by Yuzong Liu on 2011-03-14.
Copyright (c) 2011 . All rights reserved.
"""

import sys, os
import re
import string
import util
import copy
import math
from dataSequence import *


def gen_l1patterns(SequenceDataset,F,MIS,n,min_sup,Lcount):
    '''returns a list of length-1 patterns:
        each element of the list is a tuple in the form of
        (item, count, projected-Database)'''
    L1Patterns=[]

    for item in F:
        # print item
        count = 0
        projDB=[]
        for sequence in SequenceDataset:
            # print sequence
            flag, [pos,idx] = util.isItemInElement(item,sequence)
            # print flag, [pos,idx]
            count += int(flag)
            if flag:
                "locate the position in the sequence"
                seq = sequence[pos:]
                "locate the index of the position"
                seq[0] = seq[0][idx:]
                if len(seq[0]) == 1:
                    if len(seq) == 1:
                        seq =[[]]
                    else:
                        seq = seq[1:]                   
                else:
                    seq[0][0] = '_'
                if seq != [[]]:
                    i = 0
                    j = 0
                    while i < len(seq):
                        while j < len(seq[i]):
                            if seq[i][j] != '_' and Lcount[seq[i][j]] <min_sup:
                                if len(seq[i])==1:
                                    del seq[i]
                                    i-=1
                                    break
                                else:
                                    del seq[i][j]
                                    j -= 1
                            j += 1
                        i += 1
                    if seq != [['_']] and seq != [[]] and seq != []:        
                        projDB.append(seq)  
        if projDB == []:
            projDB = [[]]
        L1Patterns.append(([[item]],count,projDB))        
    return L1Patterns    
        
	    
def prefixSpan(pattern,projDB,F,min_sup,Lcount):
    nextSeqPattern = []
    output_Patterns = []
    for item in F:
        count = 0
        count1=0 #new item in first itemset
        count2=0 #new item in other itemsets
        newProjDB1 = []
        newProjDB2 = []
        "find all patterns of the form <{30}{x}>"
        for sequence in projDB:
            if sequence == [[]] or sequence == []:
                continue
            tmp = copy.deepcopy(pattern[-1])
#            if sequence == [[]] or sequence == []:
#                continue
            if sequence[0][0]=='_':
                continue
            # print item, sequence    
            flag, [pos,idx] = util.isItemInElement(item,sequence)
            # print flag, [pos, idx]
            count += int(flag)
            if flag:
                seq = sequence[pos:]
                seq[0] = seq[0][idx:]
                if len(seq[0]) == 1:
                    if len(seq) == 1:
                        seq =[[]]
                    else:
                        seq = seq[1:]
                else:
                    seq[0][0] = '_'

                if seq != [[]]:
                    i = 0
                    j = 0
                    while i < len(seq):
                        while j < len(seq[i]):
                            if seq[i][j] != '_' and Lcount[seq[i][j]] <min_sup:
                                if len(seq[i])==1:
                                    del seq[i]
                                    i-=1
                                    break
                                else:
                                    del seq[i][j]
                                    j -= 1
                            j += 1
                        i += 1

                    if seq != [['_']] and seq != [[]] and seq != []:        
                        newProjDB2.append(seq)   
                                        
                patterntmp = copy.deepcopy(pattern[-1])
                flagtmp, postmp, idxtmp = util.isContained([[item]],[patterntmp])
                if flagtmp==False:
                    patterntmp.append(item)
                    patterntmp = [patterntmp]
                    flagtmp, postmp, idxtmp = util.isContained(patterntmp, sequence)
                    count1 += int(flagtmp)
                    tmpseq = copy.deepcopy(sequence)
                    seqtmp = tmpseq[postmp:]
                    seqtmp[0] = seqtmp[0][idxtmp:]
                    if len(seqtmp[0]) == 1:
                        if len(seqtmp) == 1:
                            seqtmp =[[]]
                        else:
                            seqtmp = seqtmp[1:]
                    elif len(seqtmp[0])>1:                                
                        seqtmp[0][0] = '_'
    
                    if seqtmp != [[]]:
                        i = 0
                        j = 0
                        while i < len(seqtmp):
                            while j < len(seqtmp[i]):
                                if seqtmp[i][j] != '_' and Lcount[seqtmp[i][j]] <min_sup:
                                    if len(seqtmp[i])==1:
                                        del seqtmp[i]
                                        i-=1
                                        break
                                    else:
                                        del seqtmp[i][j]
                                        j -= 1
                                j += 1
                            i += 1
                        if seqtmp != [['_']] and seqtmp != [[]] and seqtmp != [] and seqtmp!=[[],[]]:        
                            newProjDB1.append(seqtmp)           
                             

        
        "find all patterns of the form <{30,x}> and <{_,x}>"
        for sequence in projDB:
            if sequence == [[]] or sequence == []:
                continue
            flag, [pos,idx] = util.isItemInElement(item,sequence)
            if flag:
                if sequence[0][0]=='_':
                    if pos==0:
                        count1 += int(flag)
                        tmpseq = sequence[1:]
                        flagtmp, [postmp,idxtmp] = util.isItemInElement(item,tmpseq)
                        if flagtmp:
                            count2 += int(flagtmp)
                            seqtmp = tmpseq[postmp:]
                            seqtmp[0] = seqtmp[0][idxtmp:]
                            if len(seqtmp[0]) == 1:
                                if len(seqtmp) == 1:
                                    seqtmp =[[]]
                                else:
                                    seqtmp = seqtmp[1:]
                            elif len(seqtmp[0])>1:                                
                                seqtmp[0][0] = '_'
            
                            if seqtmp != [[]]:
                                i = 0
                                j = 0
                                while i < len(seqtmp):
                                    while j < len(seqtmp[i]):
                                        if seqtmp[i][j] != '_' and Lcount[seqtmp[i][j]] <min_sup:
                                            if len(seqtmp[i])==1:
                                                del seqtmp[i]
                                                i-=1
                                                break
                                            else:
                                                del seqtmp[i][j]
                                                j -= 1
                                        j += 1
                                    i += 1
                                if seqtmp != [['_']] and seqtmp != [[]] and seqtmp != [] and seqtmp!=[[],[]]:        
                                    newProjDB2.append(seqtmp)   
                                                
                    else:
                        count2 += int(flag)
                        patterntmp = copy.deepcopy(pattern[-1])
                        flagtmp, postmp, inxtmp = util.isContained([[item]],[patterntmp])
                        if flagtmp==False:
                            patterntmp.append(item)
                            patterntmp = [patterntmp]
                            flagtmp, postmp, idxtmp = util.isContained(patterntmp, sequence)
                            count1 += int(flagtmp)
                            
                            tmpseq = copy.deepcopy(sequence)
                            seqtmp = tmpseq[postmp:]
                            seqtmp[0] = seqtmp[0][idxtmp:]
                            if len(seqtmp[0]) == 1:
                                if len(seqtmp) == 1:
                                    seqtmp =[[]]
                                else:
                                    seqtmp = seqtmp[1:]
                            elif len(seqtmp[0])>1:                                
                                seqtmp[0][0] = '_'
            
                            if seqtmp != [[]]:
                                i = 0
                                j = 0
                                while i < len(seqtmp):
                                    while j < len(seqtmp[i]):
                                        if seqtmp[i][j] != '_' and Lcount[seqtmp[i][j]] <min_sup:
                                            if len(seqtmp[i])==1:
                                                del seqtmp[i]
                                                i-=1
                                                break
                                            else:
                                                del seqtmp[i][j]
                                                j -= 1
                                        j += 1
                                    i += 1
                                if seqtmp != [['_']] and seqtmp != [[]] and seqtmp != [] and seqtmp!=[[],[]]:        
                                    newProjDB1.append(seqtmp)                        
                            
                    seq = sequence[pos:]
                    seq[0] = seq[0][idx:]
                    if len(seq[0]) == 1:
                        if len(seq) == 1:
                            seq =[[]]
                        else:
                            seq = seq[1:]
                    else:
                        seq[0][0] = '_'

                    if seq != [[]]:
                        i = 0
                        j = 0
                        while i < len(seq):
                            while j < len(seq[i]):
                                if seq[i][j] != '_' and Lcount[seq[i][j]]< min_sup:
                                    if len(seq[i])==1:
                                        del seq[i]
                                        i-=1
                                        break
                                    else:
                                        del seq[i][j]
                                        j -= 1
                                j += 1
                            i += 1
                        if seq != [['_']] and seq != [[]] and seq != []:   
                            if pos==0:     
                                newProjDB1.append(seq)   
                            else:
                                newProjDB2.append(seq)

#                else:
#                    patterntmp = copy.deepcopy(pattern[-1])
#                    patterntmp = [patterntmp]
#                    patterntmp[-1].append(item)
#                    flagtmp = util.isContained(patterntmp, sequence[1:])
#                    count1 += int(flagtmp)
                    
                    
#                    tmp = copy.deepcopy(pattern[-1])
#                    if len(sequence[0])>= len(tmp):
#                        if sequence[0][0:len(tmp)]==tmp:
#                            if idx < len(tmp):
#                                continue
#                            if pos==0:
#                                count1 += int(flag)
#                            else:
#                                count2+= int(flag)
#                            seq = sequence[pos:]
#                            seq[0] = seq[0][idx:]
#                            if len(seq[0]) == 1:
#                                if len(seq) == 1:
#                                    seq =[[]]
#                                else:
#                                    seq = seq[1:]
#                            else:
#                                seq[0][0] = '_'                                
#
#                            if seq != [[]]:
#                                i = 0
#                                j = 0
#                                while i < len(seq):
#                                    while j < len(seq[i]):
#                                        if seq[i][j] != '_' and Lcount[seq[i][j]] <min_sup:
#                                            if len(seq[i])==1:
#                                                del seq[i]
#                                                i-=1
#                                                break
#                                            else:
#                                                del seq[i][j]
#                                                j -= 1
#                                        j += 1
#                                    i += 1
#
#                                if seq != [["_"]] and seq != [[]] and seq != []:  
#                                    if pos==0:      
#                                        newProjDB1.append(seq)
#                                    else:
#                                        newProjDB2.append(seq)  
        
        if count1 >= min_sup:
            pattern2=copy.deepcopy(pattern)
            pattern2[-1].append(item)
            if newProjDB1==[]:
                newProjDB1 = [[]]
            output_Patterns.append((copy.deepcopy(pattern2),count1,copy.deepcopy(newProjDB1)))
        if (count+count2) >= min_sup:
            pattern2=copy.deepcopy(pattern)
            pattern2.append([item])
            if newProjDB2==[]:
                newProjDB2 = [[]]
            output_Patterns.append((copy.deepcopy(pattern2),count+count2,copy.deepcopy(newProjDB2)))                               
                
    return output_Patterns           
	    



def main():
    MIS = {}    # MIS Value
    SDC = 0.0    # Support DifferenceConstraint
    SequenceDataset = []    # Sequence Dataset
    SplitLine =  "***************************"
    depth = 10

    output_Pattern2 = {}
    for i in range(1,depth+1):
        output_Pattern2[i] = []

    " Data Initilization "
    MIS, SDC = util.readMISFile("paraTest.txt", MIS, SDC)
    # MIS, SDC = util.readMISFile("para.txt", MIS, SDC)
    print "MIS = " + str(MIS)
    print "SDC = " + str(SDC)
    SequenceDataset = util.readDataFile('dataTest.txt',SequenceDataset)
    # SequenceDataset = util.readDataFile('data.txt',SequenceDataset)    
    print "SequenceDataset = " + str(SequenceDataset)
    M = util.sort(MIS)
    print "M = " + str(M)
    n = len(SequenceDataset)
    
    "Length-1 seqential patterns"
    L1Patterns = gen_l1patterns(SequenceDataset,M,MIS,n)
    FreqItems = []
    F = []
    tmp = {}
    for item in L1Patterns:
        (a,b,c) = item
        FreqItems.append(a)
        tmp[a[0][0]] = b
        F.append(a[0][0])
        
    print "Length-1 Sequential Patterns: \n" +str(L1Patterns)
    print F
    output_Pattern2[1].append(L1Patterns)
    print SplitLine
    
    i = 1
    while output_Pattern2[i] != []:
        for elements in output_Pattern2[i]:  
            if elements != []:
                for elem in elements:
                    # print (pattern,count,projDB)
                    (pattern,count,projDB) = elem
                    result = prefixSpan(pattern,projDB,F,2)
                    if result != []:
                        output_Pattern2[i+1].append(result)
        i += 1                
    print output_Pattern2

if __name__ == "__main__":
    main()	    
		


